import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {}

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public void levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while(! queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur.val+" ");

            if(cur.left != null){
                queue.offer(cur.left);
            }

            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }

    public List<List<Integer>> levelOrder1(TreeNode root){
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;

        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        queue1.offer(root);

        while(! queue1.isEmpty()){
            List<Integer> curList = new ArrayList<>();
            int size = queue1.size();

            while(size != 0){
                TreeNode cur = queue1.poll();
                curList.add(cur.val);
                if(cur.left != null){
                    queue1.offer(cur.left);
                }

                if(cur.right != null){
                    queue1.offer(cur.right);
                }
                size--;
            }
            ret.add(curList);
        }
        return ret;
    }
}